The invention relates to a method for encoding symbols from a sequence of digitized images together with a corresponding decoding method. Over and above this, the invention relates to an encoding device and a decoding device for carrying out respectively the encoding or decoding method.
Video encoding methods are in general carried out in two processing stages. First, the images in the video stream are decorrelated in a suitable way, by prediction and transformation. The result of the decorrelation step is symbols in the form of transformation coefficients, motion vectors, further encoding data and the like. This is often followed by in turn a quantization of the symbols which have been generated, by which the compression efficiency is increased. In a second manipulation process, the symbols which have been generated are subjected to a loss-free entropy encoding, in which the redundancy which still exists in the generated symbols, i.e. their probabilities of occurrence and their mutual statistical dependency, is utilized to generate from the symbols the shortest possible code words, with the shortest possible overall length for the data stream.
From the related art, various methods are known for entropy encoding. In the case of VLC encoding (VLC=Variable Length Coding), each symbol which is generated is mapped bijectively onto a code word. The relationship between a symbol and the corresponding code word is then represented by a code table, such as for example a look-up table.
Another common method of entropy encoding is arithmetic encoding. Unlike VLC encoding, in which a symbol is transformed into a code word, in the case of arithmetic encoding one single code word is generated from several symbols. With arithmetic encoding, the symbols are mapped onto binary numbers, on the basis of their frequencies, so that a binary representation of the successive symbols is obtained.
In general, entropy encoding methods are based on the principle of deriving, from the frequencies of the symbols which occur, one or more probability models on the basis of which short code words are generated, i.e. the code words generated by the entropy encoding are shorter for symbols or symbol sequences which have a high frequency than for symbols or symbol sequences with a lower frequency. In general, entropy encoding methods are context-based, i.e. different types of symbols are distinguished, these representing different items of data. For these different types of symbols, the frequencies of the symbols which occur are processed separately in a specific context, and hence on the basis of a specific probability model. In video encoding methods, a context can if necessary also depend on other criteria, for example the encoding of an image region can depend on the encoding decisions for neighboring image regions in the image. Further, entropy encoding methods are often organized adaptively, i.e. during the encoding, the probability models are appropriately adapted, on the basis of the changing frequencies of the symbols which occur.
In order to increase the encoding speed of entropy encoding methods, various methods are known from the related art. In the H.264/AVC video encoding standard, the images in the video stream are divided up into so-called slices, where each slice represents a part of the image which can be encoded completely independently of the other parts. That is to say, both in the generation of the original symbols and also in the subsequent generation of the code word based on entropy encoding, there are no interdependencies between different slices. Hence, the probability models or contexts, as applicable, are not matched across slices. This leads to a lower compression efficiency.
Also known from the related art is the subdivision of video images into so-called entropy slices (see A. Segall et al., “Entropy slices for parallel entropy decoding,” (2008) (“Segall”)). Unlike the conventional slices described above, entropy slices permit dependency between the symbols, such as for example, intraprediction. Only the generation of the code words based on the entropy encoding is independent between the individual entropy slices. By the use of entropy slices, the compression efficiency is increased by comparison with conventional slices. This notwithstanding, the disadvantage remains that different statistics are used for the symbols in different entropy slices, which in turn reduces the efficiency of the entropy encoding.
X. Guo, “Ordered Entropy Slices for Parallel CABAC,” (2009) (“Guo”)describes the concept of so-called ordered entropy slices, which improve the properties of the entropy slices described above. In this case, the formation of a context for the entropy encoding is permitted across multiple entropy slices. The statistical dependencies between entropy slices are thus taken into account, so that the encoding efficiency is improved. Over and above this, the individual macroblocks in the image are not read in line-by-line during the encoding, but in a zigzag pattern. This is clarified in FIGS. 1A to 1C. These figures show different variants, conforming to Guo, of the reading in of macroblocks, where the individual macroblocks are represented by a sequence of rectangles and, for the sake of clarity, only some of them have been labeled with the reference mark MB. FIG. 1A shows line-by-line reading in of the macroblocks, as is indicated by the vertical line L1. In taking into account the context, which requires the neighboring macroblocks on the left hand, the upper left hand, the upper and the upper right hand sides to be available for the encoding of a macroblock, the problem exists with this variant that it is not possible to process several lines of macroblocks in parallel. In contrast to this, the zigzag pattern of macroblock processing, based on the line L2 as shown in FIG. 1B, permits parallel processing of two lines in each case, because the encoding of the first macroblock of the following entropy slice in the third line can start as soon as the fifth macroblock of the first pair of lines has been read in. FIG. 1C shows another variant of a zigzag pattern reading in of macroblocks, which now makes possible the processing of three lines per ordered entropy slice, as shown by the line L3.
A further variant of entropy slices is so-called interleaved entropy slices, which are described in V. Sze et al., “Massively Parallel CABAC,” (2009) (“Sze 2009”). In this case, the slices do not represent contiguous lines, but rather the lines of the individual slices are nested within one another. This is again clarified in FIGS. 2A and 2B. In this connection, FIG. 2A shows a subdivision of an image I into two conventional entropy slices SL1 and SL2, where the upper half of the image forms a contiguous slice SL1 with macroblocks MB1 and the lower portion SL2 of the image forms a contiguous slice SL2 with appropriate macroblocks MB2 (shown hatched). Unlike these conventional slices, an example of interleaved entropy slices is shown in FIG. 2B. Here, each slice concerned, SL1′ or SL2′, is formed by lines of macroblocks which are offset by one line relative to each other. The slice SL1′ in FIG. 2B is identified by unshaded macroblocks MB1′ and is formed by the first, third, fifth etc. line. On the other hand, the slice SL2′ is identified by the hatched macroblocks MB2′ and is formed by the second, fourth, sixth etc. line. Interleaved entropy slices permit the formation of contexts across multiple entropy slices. However, no common statistic is generated for the probability model used for entropy encoding.
For the purpose of improving the compression efficiency in video encoding methods, Sze 2009 describes in addition syntax element partitioning. With this, several code words are generated for different groups of syntax elements, such as for example mode data, motion vectors, transformation coefficients. Because the individual groups have different contexts, the context formation is also carried out separately. Because the relative frequencies of the different groups are different, the computing load when using parallel encoding branches for encoding is unbalanced between the individual encoding branches.
The V. Sze et al., “Parallel CABAC,” (2008) describes a special variant of an arithmetic encoding, in which two binary symbols are processed in parallel during the encoding. In this way it is possible to encode four states in one encoding cycle, instead of two. However, with this type of encoding the context formation is complex, and more operations are required per encoding cycle.